Document image information, be it color or black and white, is commonly generated in a bitmap format at a particular scale, orientation .THETA. and resolution K.times.L.times.b, corresponding to a desired printer capability, where K is a number of spots printable per unit of length in one dimension, L is a number of spots printable per unit length in the other dimension, and b is the depth of each pixel, in number of possible levels. This bitmap is present for every color separation printed at the output device, i.e., 4 bitmaps for a 4-color output device, 3 for a 3-color, 2 for a 2-color and 1 for a black and white output device. In a common example of a black and white print output, document image data comprising a bitmap to be printed is provided to a printer suitable for printing at 300 spots per inch (spi) in both dimensions, at a one bit depth giving 2 levels. Many considerations drive this single selection of resolution, including the desirability of providing only a limited number of fonts (alphanumeric bitmaps) so as to use only a limited amount of storage space. Common software packages available on personal computers or for operation of input scanners for document creation, also usually provide only a single resolution output.
Increasingly, the resolution available from printers varies over a wider range of choices. Printer resolutions are available over a range, for example, from less than 200 spi to more than 600 spi. Resolutions vary for a number of reasons, generally related to the quality of the output image. Simply printing a 300 spi bitmap at 400 spi or 600 spi is undesirable however, since the image will be reduced substantially in size on the output page or display. It would be highly desirable to provide the capability of printing color documents at any resolution.
Most documents can be classified as having pictures and text or line art. Pictures or pictorial images, are represented in such systems with varying levels of gray to capture detailed content. If the image has been scanned at an image input terminal, the gray levels will be voltage gradations varying between a minimum and a maximum. If the image is further halftoned, the pictorial image will be represented through the use of dithering or halftoning processes. In such arrangements, over a given area having a number of gray pixels therein, each pixel value of an array of gray pixels within the area is compared to one of a set of preselected thresholds (the thresholds are stored as a dither matrix and the repetitive pattern generated by this matrix is considered a halftone cell) as taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is gray, some of the thresholds within the dither matrix will be exceeded, i.e. the image value at that specific location is larger than the value stored in the dither matrix for that same location, while others are not. In the binary case, the pixels or cell elements for which the thresholds are exceeded might be printed as black, while the remaining elements are allowed to remain white, dependent on the actual physical quantity described by the data.
Text or line art is represented in color systems as areas where all the pixels are at a minimum or maximum. In a black and white, 256 level graphics system, text and line art would be represented typically by either a 0 or 255, where each level represents a distinct gray between black and white. In color systems, black may be alternatively represented as either black or white, or as equal amounts of cyan, magenta and yellow colorants, which together form gray. If the text is colored, colors will usually be uniform throughout the text area.
It is highly desirable to use a halftoning process that preserves gray density in rendering pictorial images. Algorithms that convert gray images to binary or other number of level images for printing and which attempt to preserve the local density exist, and include among them error diffusion, as taught, for example, in "An Adaptive Algorithm for Spatial Greyscale" by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77 (1976) (hereinafter, "Floyd and Steinberg"). Another, more elaborate method would be the error diffusion techniques of U.S. Pat. No. 5,045,952, entitled "Method for Edge Enhanced Error Diffusion Algorithm" by R. Eschbach, which serves to provide image dependent edge enhancement, assigned to the same assignee as the present invention. Error diffusion attempts to maintain gray by making the conversion from gray pixels to binary or other level pixels on a pixel-by-pixel basis. The procedure examines each pixel with respect to a threshold, and the difference between the gray level pixel value and the output value is forwarded to a selected group or set of neighboring pixels, in accordance with a weighting scheme. Such forwarding of error is undesirable in the case of text, which requires sharp contrast at edges of legibility. Generally speaking, preservation of accurate gray density is not an important factor in rendering text. Other error diffusion methods include, "On the Error Diffusion Technique for Electronic Halftoning" by Billotet-Hoffmann and Bryngdahl, Proceedings of the SID, Vol. 24/3, (1983), pp. 253-258; and U.S. patent application Ser. No. 07/821,125 entitled " Method for Image Conversions With Error Diffusion", by R. Eschbach, (EPC 0 481 812 A2). A technique related to error diffusion is taught in the MAE (Minimum Average Error) method of error diffusion described in "Images from Computers", by M. Schroeder, IEEE Spectrum, March 1969, pp. 66-78, in which an error correction is performed that only affects a local neighborhood. This method does not preserve the gray density.
Segmentation of images based on image content as a means to determine optimal image processing is known, as shown in U.S. Pat. No. 4,811,115 to Lin et al, U.S. Pat. No. 4,194,221 to Stoffel and U.S. patent application Ser. No. 07/722,568 to Shiau et al., assigned to the same assignee as the present invention. However, all of these methods use variations of the auto correlation function to determine whether certain frequencies of halftones are present. GB 2,153,619A provides a similar determination of the type of image data. However in that case, a threshold is applied to the image data at a certain level, and subsequent to thresholding the number of transitions from light to dark within a small area is counted. The system operates on the presumption that data with a low number of transitions after thresholding is probably a high frequency halftone or continuous tone image. The thresholding step in this method has the same undesirable effect as described for Stoffel.
Of background interest in this area are U.S. Pat. No. 4,556,918 to Yamazaki et al. showing an arrangement assuming a periodicity of an area of halftone dots which are thresholded against an average value derived from the area to produce a density related video signal; U.S. Pat. No. 4,251,837 to Janeway, Ill., which shows the use of a three decision mode selection for determining threshold selection based on gradient constants for each pixel; U.S. Pat. No. 4,578,714 to Sugiura et al. which shows random data added to the output signal to eliminate pseudo-outlines; U.S. Pat. No. 4,559,563 to Joiner, Jr. suggests an adaptive prediction for compressing data based on a predictor which worked best for a previous pixel block; and U.S. Pat. No. 3,294,896 to Young, Jr. teaches the usefulness of thresholding in producing an image from a binary digital transmission system.
U.S. Pat. No. 4,509,195 to Nadler describes a method for binarization of a pattern wherein two concentric rings around a pixel are evaluated to determine contrast values, and the contrast values are used then to determine whether the pixel and the surrounding areas have a light or dark quality. U.S. Pat. No. 4,547,811 to Ochi et al. teaches a method of processing gray level values, depending on the density level of blocks of pixels, and their difference from a minimum or maximum value. The blocks are then processable by a halftone processing matrix depending on the difference value. U.S. Pat. No. 4,730,221 to Roetling discloses a screening technique where values of gray over an image are evaluated to determine a minimum and maximum level, in order to determine constant levels of gray. U.S. Pat. No. 4,736,253 to Shida discloses a method of producing a halftone dot by selectively comparing image signals with highlight and shadow reference values, for determination of the binarization process.
Study of documents created by users of color printing systems yields certain interesting phenomenon. First, even when color pictures are present in a document, for the most part, black text is used. Further, in the unusual case that black text is not used, the color in which text is rendered does not vary within a given area. Thus, when text is used, an examination of a given area of a color document including text will show either a) high correlation within the area within the separation, and b) high correlation between separations. Pictorial areas do not show such correlations. FIG. 1A and FIG. 1B show examples of small areas of documents, illustrating this observation. Note that the colors are given in terms of an additive system, commonly used in scanners and for displays, but a subtractive system, commonly used in printers, gives the same results.
All of the references cited herein are incorporated by reference for their teachings.